Codeforces Round #842 (Div. 2)【A - E】

五十分钟四题 1A 下班，赛后补了下 E 。

比赛链接：https://codeforces.com/contest/1768

A. Greatest Convex

题解

$x! + (x - 1)! = (x + 1) \cdot (x - 1)!$

当 $x = k - 1$ 时，原式为 $k \cdot (k - 2)!$ ，显然为 $k$ 的倍数。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int k;
        cin >> k;

        cout << (k - 1) << "\n";
    }

    return 0;
}

B. Quick Sort

题解

找以 1 开头的最长连续上升子序列，其他数都需要操作后移到尾部，次数即对 $k$ 取上整。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }

        int cnt = n, val = 1;
        for (int i = 0; i < n; i++) {
            if (p[i] == val) {
                val++;
                cnt--;
            }
        }
        cout << (cnt + k - 1) / k << "\n";
    }

    return 0;
}

C. Elemental Decompress

题解

如果有数出现三次则无解。

否则，将第一次出现的数和第二次出现的数分别赋给 $p, q$ ，其余位置的数用 set 的 upper_bound 贪心查找即可。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n), cnt(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            --a[i];
            cnt[a[i]] += 1;
        }

        bool ok = true;
        for (int i = 0; i < n; i++) {
            if (cnt[i] >= 3) {
                ok = false;
                break;
            }
        }

        if (not ok) {
            cout << "NO" << "\n";
            continue;
        }

        vector<int> p(n, -1), q(n, -1);
        vector<bool> vis(n);
        for (int i = 0; i < n; i++) {
            if (not vis[a[i]]) {
                p[i] = a[i];
                vis[a[i]] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            if (vis[a[i]] and p[i] == -1) {
                q[i] = a[i];
            }
        }

        auto fill_blank = [&](vector<int>& p, vector<int>& q) {
            set<int> st;
            for (int i = 0; i < n; i++) {
                st.insert(i);
            }
            for (int i = 0; i < n; i++) {
                st.erase(p[i]);
            }
            for (int i = 0; i < (int)p.size(); i++) {
                if (p[i] == -1 and q[i] != -1) {
                    auto it = st.upper_bound(q[i]);
                    if (it == st.begin()) {
                        ok = false;
                        return;
                    }
                    --it;
                    p[i] = *it;
                    st.erase(it);
                }
            }
        };
        
        fill_blank(p, q);
        fill_blank(q, p);

        if (not ok) {
            cout << "NO" << "\n";
        } else {
            cout << "YES" << "\n";
            for (int i = 0; i < n; i++) {
                cout << p[i] + 1 << " \n"[i == n - 1];
            }
            for (int i = 0; i < n; i++) {
                cout << q[i] + 1 << " \n"[i == n - 1];
            }
        }

    }

    return 0;
}

D. Lucky Permutation

题解

只有一个逆序对即交换升序排列中的某对相邻值。

找出 $p$ 中的所有循环节，长度为 $k$ 的循环节需要 $k - 1$ 次操作使得每个值回到自己对应的位置上。

若某个循环节里存在相邻值，则最后排为升序时可以减少一次操作来使这两个相邻值形成逆序。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            --p[i];
        }

        int ans = 0;
        bool ok = false;

        vector<bool> vis(n);
        for (int i = 0; i < n; i++) {
            if (vis[i]) {
                continue;
            }
            vector<int> v;
            int j = i, res = -1;
            while (not vis[j]) {
                vis[j] = true;
                v.push_back(p[j]);
                j = p[j];
                res += 1;
            }
            sort(v.begin(), v.end());
            for (int j = 0; j + 1 < (int)v.size(); j++) {
                if (v[j] + 1 == v[j + 1]) {
                    ok = true;
                }
            }
            ans += res;
        }

        cout << (ans + (ok ? -1 : 1)) << "\n";
    }

    return 0;
}

E. Partial Sorting

题解

• 当 $[1, n]$ 在后 $n$ 个位置或 $[2n + 1, 3n]$ 在前 $n$ 个位置时需要操作 $3$ 次
• 当 $[1, n]$ 在前 $2n$ 个位置或 $[2n + 1, 3n]$ 在后 $2n$ 个位置时需要操作 $2$ 次
• 当前 $n$ 个位置已有序或后 $n$ 个位置已有序时需要操作 $1$ 次
• 当 $3n$ 个位置整体有序时不需要操作

由于不好单独计算某一操作次数的排列数，可以用容斥原理从低到高依次计算。

• 操作 $0$ 次， $3n$ 个位置整体有序， $1$ 种情况
• 操作 $\le 1$ 次：
  • 前 $n$ 个位置有序：共有 $2n!$ 种情况
  • 后 $n$ 个位置有序：共有 $2n!$ 种情况
  • 二者交集，即前后 $n$ 个位置都有序，此时只有 $[n + 1, 2n]$ 在中间 $n$ 个位置排列，共有 $n!$ 种情况
  • 所以共有 $2 \cdot 2n! - n!$ 种情况
• 操作 $\le 2$ 次：
  • $[1, n]$ 在前 $2n$ 个位置，共有 $C_{2n}^{n} \cdot n! \cdot 2n!$ 种情况
  • $[2n + 1, 3n]$ 在后 $2n$ 个位置，共有 $C_{2n}^{n} \cdot n! \cdot 2n!$ 种情况
  • 二者交集，即 $[1, n]$ 在前 $2n$ 个位置，同时 $[2n + 1, 3n]$ 在后 $2n$ 个位置：
    • 设 $[1, n]$ 在前 $n$ 个位置中有 $i$ 个，那么在中间 $n$ 个位置中有 $n - i$ 个，共有 $C_{n}^{i} \cdot C_{n}^{n - i} \cdot n!$ 种情况
    • 此时 $[2n + 1, 3n]$ 需要填补前 $n$ 个位置中 $n - i$ 个空缺，同时在后 $2n - (n - i)$ 个位置中选取 $i$ 个位置，共有 $C_{2n - (n - i)}^{i} \cdot n!$ 种情况
    • 最后 $[2n + 1, 3n]$ 填补后 $2n$ 个位置中余下的 $n$ 个位置，共有 $n!$ 种情况
    • 所以共有 $2 \cdot C_{2n}^{n} \cdot n! \cdot 2n! - \sum \limits _{i = 0} ^{n} (C_{n}^{i} \cdot C_{n}^{n - i} \cdot n!) \cdot (C_{2n - (n - i)}^{i} \cdot n!) \cdot (n!)$ 种情况
• 操作 $\le 3$ 次：
  • 共有 $3n!$ 种情况

依次相减得出操作次数等于 $i$ 次的情况数 $cnt_i$ ，答案即 $\sum \limits _{i = 1} ^{3} i \cdot cnt_i$ 。

代码

#include <bits/stdc++.h>
using namespace std;

int MOD = 998244353;

int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(MOD - x)); }
    Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
    Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
    Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
    Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
    friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
    friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
    friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};

struct Combination {
    vector<Z> fac, inv;

    Combination(int n) : fac(n), inv(n) {
        fac[0] = 1;
        for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i;
        inv[n - 1] = fac[n - 1].inv();
        for (int i = n - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1);
    }

    Z C(int n, int m){
        if(m < 0 or m > n) return 0;
        return fac[n] * inv[m] * inv[n - m];
    }

    Z A(int n, int m){
        if(m < 0 or m > n) return 0;
        return fac[n] * inv[n - m];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n >> MOD;

    Combination C(3 * n + 1);

    Z cnt0 = 1;

    Z cnt1 = Z(2) * C.fac[2 * n] - C.fac[n] - cnt0;

    Z cnt2 = Z(2) * C.C(2 * n, n) * C.fac[n] * C.fac[2 * n] - cnt1 - cnt0;
    for (int i = 0; i <= n; i++) {
        cnt2 -= C.C(n, i) * C.C(n, n - i) * C.C(2 * n - (n - i), i) * C.fac[n] * C.fac[n] * C.fac[n];
    }

    Z cnt3 = C.fac[3 * n] - cnt2 - cnt1 - cnt0;

    cout << (cnt1 + 2 * cnt2 + 3 * cnt3).val() << "\n";

    return 0;
}